﻿#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a first-in, first-out collection of objects, where elements can be accessed
    /// from anywhere in the queue.
    /// </summary>
    /// <typeparam name="T">The type of the data in the collection.</typeparam>
    /// <remarks>The data structure has been implemented using <see cref="LinkedList{T}"/>, so it inherits
    /// the same limitations as a <see cref="LinkedList&lt;T&gt;"/> has.</remarks>
    [Serializable]
    public class RandomAccessQueue<T> : IQueue<T>
    {
        private readonly LinkedList<T> _store;
        [NonSerialized] private object _syncRoot;

        /// <summary>
        /// Initializes a new instance of the <see cref="RandomAccessQueue&lt;T&gt;"/> class.
        /// </summary>
        public RandomAccessQueue()
        {
            _store = new LinkedList<T>();
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="RandomAccessQueue&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="collection">The collection whose elements are copied to a new <see cref="RandomAccessQueue&lt;T&gt;"/>.</param>
        public RandomAccessQueue(IEnumerable<T> collection)
        {
            _store = new LinkedList<T>();
            using (IEnumerator<T> enumerator = collection.GetEnumerator())
            {
                while (enumerator.MoveNext())
                {
                    Enqueue(enumerator.Current);
                }
            }
        }

        /// <summary>
        /// Gets or sets the item at the specified index.
        /// </summary>
        /// <value>The item to access from the queue.</value>
        public T this[int index]
        {
            get
            {
                int i = 0;
                LinkedListNode<T> node = _store.First;
                while (i < Count)
                {
                    if (i == index)
                        if (node != null) return node.Value;
                    if (node != null) node = node.Next;
                    i++;
                }
                return default(T);
            }
            set
            {
                int i = 0;
                LinkedListNode<T> node = _store.First;
                while (i < Count)
                {
                    if (i == index)
                    {
                        if (node != null) node.Value = value;
                        break;
                    }
                    if (node != null) node = node.Next;
                    i++;
                }
            }
        }

        #region IQueue<T> Members

        void ICollection.CopyTo(Array array, int index)
        {
            CopyTo((T[]) array, index);
        }

        /// <summary>
        /// Gets the total number of elements in the queue.
        /// </summary>
        public int Count
        {
            get { return _store.Count; }
        }

        /// <summary>
        /// Gets an object that can be used to synchronize access to the collection.
        /// </summary>
        public object SyncRoot
        {
            get
            {
                if (_syncRoot == null)
                {
                    Interlocked.CompareExchange<object>(ref _syncRoot, new object(), null);
                }
                return _syncRoot;
            }
        }

        /// <summary>
        /// Gets a value indicating whether access to the <see cref="RandomAccessQueue&lt;T&gt;"/>
        /// is synchronized (thread safe).
        /// </summary>
        public bool IsSynchronized
        {
            get { return false; }
        }

        /// <summary>
        ///   Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        ///   A <see cref = "IEnumerator&lt;T&gt;" /> that can be used to iterate through the collection.
        /// </returns>
        public IEnumerator<T> GetEnumerator()
        {
            return _store.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        /// <summary>
        /// Enqueues the specified item to the <see cref="RandomAccessQueue&lt;T&gt;"/>.
        /// </summary>
        /// <param name="item">The item to enqueue.</param>
        public void Enqueue(T item)
        {
            var node = new LinkedListNode<T>(item);
            _store.AddLast(node);
        }

        /// <summary>
        /// Dequeues the peek element.
        /// </summary>
        /// <returns>The removed element.</returns>
        public T Dequeue()
        {
            T value = Peek();
            _store.RemoveFirst();
            return value;
        }

        /// <summary>
        /// Fetches the top element from the queue.
        /// </summary>
        /// <returns>The top element.</returns>
        public T Peek()
        {
            if (_store.First != null)
                return _store.First.Value;
            return default(T);
        }

        /// <summary>
        /// Clears the queue by removing all of its elements.
        /// </summary>
        public void Clear()
        {
            _store.Clear();
        }

        /// <summary>
        /// Copies the elements of the queue to an array of type <typeparamref name="T"/>
        /// , starting at the specified array index.
        /// </summary>
        /// <param name="array">The one-dimensional array of type <typeparamref name="T"/> that is the destination of
        /// the elements copied from the queue. The array must have zero-based indexing.
        ///	 </param>
        /// <param name="index">The zero-based index in array at which copying begins.</param>
        public void CopyTo(T[] array, int index)
        {
            _store.CopyTo(array, index);
        }

        /// <summary>
        /// Determines whether the queue contains the specified item.
        /// </summary>
        /// <param name="item">The item to search.</param>
        /// <returns>
        /// 	<c>true</c> if the queue contains the specified item; otherwise, <c>false</c>.
        /// </returns>
        public bool Contains(T item)
        {
            return _store.Find(item) != null;
        }

        #endregion

        /// <summary>
        /// Gets the last element in the queue.
        /// </summary>
        /// <returns></returns>
        public T Tail()
        {
            if (_store.Last != null)
                return _store.Last.Value;
            return default(T);
        }

        /// <summary>
        /// Adds the specified item after <paramref name="before"/>.
        /// </summary>
        /// <param name="before">The element after which <paramref name="item"/> has to add.</param>
        /// <param name="item">The item to add in the queue.</param>
        public void AddAfter(T before, T item)
        {
            LinkedListNode<T> node = _store.Find(before);
            _store.AddAfter(node, item);
        }

        /// <summary>
        /// Adds the specified item before <paramref name="after"/>.
        /// </summary>
        /// <param name="after">The element before which <paramref name="item"/> has to add.</param>
        /// <param name="item">The item to add in the queue.</param>
        public void AddBefore(T after, T item)
        {
            LinkedListNode<T> node = _store.Find(after);
            _store.AddBefore(node, item);
        }

        /// <summary>
        /// Removes an element at a specified index.
        /// </summary>
        /// <param name="index">The position of the element to remove.</param>
        public void RemoveAt(int index)
        {
            T node = this[index];
            _store.Remove(node);
        }

        /// <summary>
        /// Removes the specified item from the queue.
        /// </summary>
        /// <param name="item">The item to remove from the queue.</param>
        public void Remove(T item)
        {
            _store.Remove(item);
        }
    }
}